package com.zhugang.week02;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @program algorithms
 * @description: reverseKGroup
 * @author: chanzhugang
 * @create: 2022/05/30 22:49
 */
public class ReverseKGroup {

    /**
     * 25. K个一组翻转链表
     *
     * @param head
     * @param k
     * @returns
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 遍历链表，每k个节点翻转一次：用栈实现（每k个节点压入栈）
        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode dummy = new ListNode(0, null);
        ListNode p = dummy;
        while (true) {
            int count = 0;
            ListNode temp = head;
            while (temp != null && count < k) {
                stack.add(temp);
                temp = temp.next;
                count++;
            }
            if (count != k) {
                // 无需翻转
                p.next = head;
                break;
            }
            while (!stack.isEmpty()) {
                // 翻转每组链表
                p.next = stack.pollLast();
                p = p.next;
            }
            // p指向下一组节点
            p.next = temp;
            head = temp;
        }
        return dummy.next;
    }

    public ListNode reverseKGroup2(ListNode head, int k) {
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;
        ListNode p = head;
        while (p != null) {
            int count = 0;
            ListNode q = p;
            while (q != null) {
                count++;
                if (count == k) {
                    break;
                }
                q = q.next;
            }
            if (q == null) {
                tail.next = p;
                return dummyHead.next;
            } else {
                ListNode temp = q.next;
                ListNode[] nodes = reverse(p, q);
                tail.next = nodes[0];
                tail = nodes[1];
                p = temp;
            }

        }
        return dummyHead.next;
    }

    private ListNode[] reverse(ListNode head, ListNode tail) {
        ListNode newHead = null;
        ListNode p = head;
        while (p != tail) {
            ListNode temp = p.next;
            p.next = newHead;
            newHead = p;
            p = temp;
        }
        tail.next = newHead;
        newHead = tail;
        return new ListNode[]{tail, head};
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}